The invention pertains to a method and apparatus for performing data base searches among data stored in a disk file system. A typical computer system in which data base searches are to be performed includes a main or host processing system, having a central processing unit and one or more high speed random access memories connected to the host processor, and one or more disk file memories, also connected to the host processor. The high speed main memory is utilized for executing operating programs and the like, while the lower speed disk file memories are utilized for storing large amount of "raw" or base data.
Data is stored in the disk file memories as a series of data records, each of a fixed number of bytes. When it is desired to perform a data base search of data located within the disk file memories, a "key" or search argument is compared with specified portions of the data read out from the disk file memories.
In the prior art, such data base searches were most commonly performed by first reading a predetermined number of data records from the disk file memories into the main memory and performing the actual comparison operation between the key or search argument and the specified portions of the data records within the host processor. This was of course a slow and hence costly operation. Much time was required in reading the data from the disk file memories into the main memory and in then performing the comparison operation within the host processor. The host processor could not be utilizdd for other tasks during any of this time.
U.S. Pat. No. 3,243,783 issued Mar. 21, 1966 to Rabenda et al., describes a file search system of this basic type. In that system, certain records are selected from a group of records and read into main storage with remaining records skipped. However, the host processor is still engaged and unavailable for other processing operations during the entire search operation.
U.S. Pat. No. 3,350,694, issued Oct. 31, 1967 to Kusnick et al., describes a search system in which search requests are re-ordered in a key storage to continually present the best accessing sequence to a readout transducer. The readout transducer can then extract the desired information from the disk file memories in an order which minimizes the time that the main processor is engaged. As in the previously discussed case, however, the central processor is unavailable for other tasks during the entire search operation.
Similarly, U.S. Pat. No. 3,408,631, issued Oct. 29, 1968 to Evans et al., describes a record search system in which rotational delays, that is, delays in reading data from the disk file memories due to the time required to rotate the disks to the desired starting position, are minimized. According to that system, the transfer of a desired record to its associated electronic data processor (EDP) is accomplished during a single traverse of the record. After the access mechanism has been positioned in the disk file unit, a record start signal begins the comparison process between the subsequent data signals and the search argument held in the associated EDP. The actual comparison is performed in the file control unit. The disk file control unit signals the EDP when the argument and the data signals are equal. Additionally, the file control unit can be instructed to signal the EDP when the comparison between the search argument and the data signals is either high or low. The EDP then initiates the subsequent transfer of the desired record from the bulk storage unit. No rotational delay exists when the key signals precede the data signals in the record. Therefore, the EDP is only involved with the record retrieval operation for a minimum time duration. Nevertheless, the main processor (the EDP) is still unavailable for other processing operations during the whole record search operation.
U.S. Pat. No. 3,629,860, issued Dec. 21, 1981 to Capozzi, teaches a record locating apparatus for variable length records on magnetic disk units. In one embodiment of this system, the apparatus determines the length of time required for each selected record position to reach its respective read/write head, and in the event considerable delay would be encountered, it freezes the channel and control unit for other processing work during the delay. Although the overall time for completing the record search operation may be reduced to the utilizing system, the main processor is still engaged during the entire active period of the record search operation, that is, during the actual searching of the records once they have been read into the main storage.
U.S. Pat. No. 3,848,235, issued Nov. 12, 1974 to Lewis et al., teaches a scan and control apparatus for a disk storage drive in which disk storage rotational delays are eliminated where the records on the disk media do not have a separate key field with a gap between the key and data fields. This is accomplished by providing a decode apparatus for detecting a hexadecimal FF transferred from the scan data field in main storage to the disk storage drive attachment. The scan data field in the main storage contains the search key at the head of the field and the remainder of the field is filled with hexadecimal FF. The scan operation takes place by transferring the scan data field from main storage a bit at a time in comparing the search key for main storage with the key in the disk data field. The comparison takes place until the disk storage drive detects a hexadecimal FF. This indicates the comparison operation is complete and sets the operation from a scan mode to a read mode whereby, if the key of the disk data field is equal to the search key, the remaining bits of the disk data field are transferred into the scan data field in main storage with one hexadecimal FF between the search key and the scan field and the newly transferred bits from the disk data field. The single hexadecimal FF functions to absorb the switching time for changing from a scanning to a read mode while still delineating the end of the search key.
In all of the above systems, although some delays are eliminated, still the main processing unit (host processor) is engaged and unavailable for performing processing operation during substantially the entire record scanning operation. Also, these systems generally require an amount of main storage sufficient to hold all of the data records which it may desired to search. In many instances, this may mandate a much larger size for the main storage than would be required for only the execution of operating programs and the like.
Accordingly, it is a primary object of the present invention to provide a record scanning method and apparatus in which the main or host processor is free to perform other tasks while the record scanning operation is taking place.
More specifically, it is an object of the invention to provide such a record scanning method and apparatus in which the host processor can simply transfer to an outboard record scanning circuit the parameters necessary to perform the record search and later receive from the record scanning circuit the results of the search. In the desired method and apparatus, from the time that the host processor instructs the record scanning circuit as to the parameters of the search to be performed until the time that the record scanning circuit reports the results of the search to the host processor, the host processor is free to perform other tasks.